package datastructures.stacks;

import java.util.Iterator;
import java.util.NoSuchElementException;

import lib.LinearNode;

/**
 * Design Note
 *
 * 1. There is a node reference.
 * 2. There is an int type variable to count the number of elements in the stack
 * 3. Linked structure is used.
 * 4. There is at least one node which is dummy node
 * 5. Generic type is used.
 * 6. Return null if the stack is empty when peek or pop is executed.
 *
 * @author Gatsby Lee
 *
 * @param <T>
 */
public class LinkedStackWithSentinelNode<T> implements StackADT<T> {

	private LinearNode<T> first;
	private int size;

	public LinkedStackWithSentinelNode() {
		this.first = new LinearNode<T>(null);
		this.size = 0;
	}

	@Override
	public void push(T element) {
		// Create a new node
		LinearNode<T> node = new LinearNode<T>(element);
		node.setNext(this.first);
		this.first = node;
		this.size++;
	}

	@Override
	public T pop() {
		if (this.size == 0) {
			return null;
		}
		T element = this.first.getElement();
		this.first = this.first.getNext();
		this.size--;
		return element;
	}

	@Override
	public T peek() {
		if (this.size == 0) {
			return null;
		}
		return this.first.getElement();
	}

	@Override
	public boolean isEmpty() {
		if (this.size == 0) {
			return true;
		}
		return false;
	}

	@Override
	public int size() {
		return this.size;
	}

	public Iterator<T> iterator() {
		return new ReverseLinkedIterator();
	}

	private class ReverseLinkedIterator implements Iterator<T> {

		private LinearNode<T> firstForIterator = first;

		@Override
		public boolean hasNext() {
			if (this.firstForIterator.getNext() == null) {
				return false;
			}
			return true;
		}

		@Override
		public T next() {
			if (this.firstForIterator.getNext() == null) {
				throw new NoSuchElementException();
			}
			this.firstForIterator = this.firstForIterator.getNext();
			return this.firstForIterator.getElement();
		}

		/**
		 * This method is not supported
		 */
		@Override
		public void remove() {
			throw new UnsupportedOperationException();
		}
	}
}
